This invention relates to the field of computer image processing. More specifically, the invention relates to the field of level-of-detail selection for rendering.
A large portion of the computer graphics literature deals with the rendering problem. For a scene S, composed of modeling primitives (e.g., triangles, spheres, cars), rendering consists of computing a visual representation of the primitives given an eye position, a view direction, and a field of view. Foley et al., xe2x80x9cComputer Graphics, Principles and Practicexe2x80x9d, Second Edition, Addison-Wesley, Reading, Mass., 1990, which is here incorporated by reference in its entirety, contains further details about rendering.
There are several factors that contribute to the complexity of rendering a scene S. Two important ones are the total number of modeling primitives, and the complexity of each primitive, which can be measured in several ways, for instance, as the number of triangles that define the given primitive.
Resource limitations led inventors to propose several techniques for optimizing the rendering process. One such technique is proposed in U.S. patent application xe2x80x9cSYSTEM, PROGRAM PRODUCT AND METHOD OF RENDERING A THREE DIMENSION IMAGE ON A DISPLAYxe2x80x9d, Ser. No. 09/296,077, filed Apr. 29, 1999, by J. Klosowski and C. Silva, which is here incorporated by reference in its entirety, where a technique for visibility estimation is proposed.
Another popular technique, originally proposed by J. Clark, xe2x80x9cHierarchical geometric models for visible surface algorithmsxe2x80x9d, Communications of the ACM, 19(10):547-554, October 1976, for rendering optimization consists of generating several xe2x80x98level-of-detailxe2x80x99 representations for each modeling primitive. Originally, a modeling primitive is specified in full detail, also known as full-resolution. Prior art simplification algorithms, which are surveyed in xe2x80x9cSurvey of polygonal surface simplification algorithmsxe2x80x9d, in Multiresolution Surface Modeling Course Notes, ACM SIGGRAPH, 1997, by Paul S. Heckbert and Michael Garland, (this survey is here incorporated by reference in its entirety), can be applied to the full-resolution model to reduce the rendering complexity, while still providing reasonable visual fidelity to the original full-resolution model. Using the simplification methods, several level-of-detail representations can be generated for a model, ranging from the full-resolution model, with the greatest rendering complexity, to a very simplified model, with the least rendering complexity. At render time, a single level-of-detail representation is selected for each modeling primitive in an attempt to lower the total rendering cost of the scene, while keeping the visual quality of the final image high. A simple example of this idea is to have different representations for a car, and when the user is looking at it from far away using a simpler representation, since the user will not be able to distinguish fine details of the car anyway, than when the car is nearby, and more details of the car will be visible to the user.
The prior art lacks a technique for level-of-detail selection that is based upon visibility information. Rather, prior art techniques base their level-of-detail selection on simple geometric facts, such as screen-space coverage. This coupling of visibility information and level-of-detail representation would provide improved image quality over the prior art at the same rendering cost.
An object of this invention is an improved system and method for selecting portions of geometry, and their level-of-detail representation to be rendered in an image processing system.
An object of this invention is an improved system and method for selecting portions of geometry and their level-of-detail representation to be rendered within budget constraints.
The present invention is a technique and system for selecting level-of-detail representations of geometric models to be rendered within an image processing system.
For each modeling primitive, xe2x80x98fractionalxe2x80x99 visibility estimations are computed, thereby ranking how likely it is that a modeling primitive is visible, given the current viewing position, view direction, and field of view. Using these rankings, an appropriate level-of-detail for each modeling primitive is selected to optimize the rendering process by reducing the overall rendering complexity of the scene S, e.g., by reducing the total number of triangles that need to be rendered, while preserving the quality of the final image produced and displayed upon the screen.
The present invention includes two main steps: (1;) a visibility estimation process; and (2) a level-of-detail selection process.
The visibility estimation process provides estimates, e.g., probabilities, as to how likely it is that each of the modeling primitives in a given scene are visible for the current viewing parameters. In the preferred embodiment, this process is the Prioritized-Layered Projection (PLP) technique discussed in U.S. patent application Ser. No. 09/296,077 incorporated above. The PLP method can provide visibility estimations on a per model basis or upon a per cell basis, where, as described in the aforementioned patent application, the union of all cells provide a subdivision of the space occupied by the models in the scene.
The level-of-detail selection process determines which representations of the models will be rendered to produce the displayed image. Level-of-detail is utilized when the capabilities of the imaging system are not sufficient to render the full-resolution models within a specific budget B, e.g., a specified amount of time. Visibility estimates v1, v2, . . . , vN, are provided for N modeling primitives m1, m2, . . ., mN. In the preferred embodiment, the visibility estimates are fractions between 0.0 and 1.0, and will sum to 1.0, although alternative visibility estimates could also be used and then scaled appropriately. Level-of-detail selection can be accomplished on a per model basis by choosing the best representation of the model i that is constrained to the budget of (B times vi). In other words, each modeling primitive is assigned a fraction of the budget B that is directly proportional to its likelihood of being visible. The budget can be either a time constraint or a number of triangles. Since each model will obey its allocated budget, the global budget B for the imaging system will also be met.